package com.ccsoft.leetcode.service;

import com.ccsoft.leetcode.model.TreeNode;
import org.springframework.stereotype.Service;

/**
 * 2021年11月20日 08:04:49 chanchaw
 * 100. 相同的树
 */
@Service
public class SameTree {

    private boolean ret = true;
    public boolean isSameTree(TreeNode p, TreeNode q) {
        ret = true;
        recursion(p,q);
        return ret;
    }

    public void recursion(TreeNode p, TreeNode q){
        if( !ret ) return;

        // 案例数据：{1},{1,null,2}。要求判断 left 节点时要有空判断
        Result result = checkNull(p,q);
        if( result.exit ) {
            ret = result.compared;
            if( result.exit ) return;
            if( !ret ) return;
        }

        if( p.val != q.val ) {
            ret = false;
            return;
        }

        TreeNode pLeft = p.left;
        TreeNode qLeft = q.left;
        result = checkNull(pLeft,qLeft);
        if( result.exit ) {
            ret = result.compared;
//            if( result.exit ) return; 两个节点的 left 都是 null 但是还有 right 要判断，所以不可直接退出
            if( !ret ) return;
        }
        recursion(pLeft,qLeft);
        if( !ret ) return;// 积极断路逻辑配合递归要在每个分支后做判断，防止后面的逻辑修改全局标识

        TreeNode pRight = p.right;
        TreeNode qRight = q.right;
        result = checkNull(pRight,qRight);
        if( result.exit ) {
            ret = result.compared;
            if( result.exit ) return;
            if( !ret ) return;
        }
        recursion(pRight,qRight);
    }

    public Result checkNull(TreeNode p, TreeNode q){
        if( p == null && q == null ) return new Result(true,true);
        if( p == null && q != null ) return new Result(false,true);
        if( p != null && q == null) return new Result(false,true);
        return new Result(true,false);
    }

    public class Result {
        boolean compared;
        boolean exit;

        public Result(boolean compared, boolean exit) {
            this.compared = compared;
            this.exit = exit;
        }
    }

    // 一开始使用了内部类，代码集中，简单方便，但是使用 post 测试时报无没有参数的构造函数的异常
    // 之后将模型类独立到包 model 下
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;
//        }
//    }
}
